package 动态规划.另类的;
import java.util.List;
import java.util.LinkedList;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
public class leetcode131分割字符串 {
	
	public static void main(String []args) {
		System.out.println(solution("aab"));
		System.out.println(solutionAgain("aab"));
//		System.out.println();
	}
		public static boolean isPalindrome(String s,int start,int end) {
			 char []str= s.toCharArray();
			for(int l = start ,r=end;l < r; l++,r--) {
				if(str[l] != str[r]) {
					return false;
				}
			}
			return true;
		}
		public static List<LinkedList<String>> solution(String s){
			 LinkedList<String> path =new LinkedList<>();
			 List<LinkedList<String>> ans =new ArrayList<>();
			 if(s == null) {
				 return ans;
			 }
			 process(0,path,ans,s);
			 return ans;
		}
		public static void process(int index,LinkedList<String> path,List<LinkedList<String>> ans
,String s) {
			if(index == s.length()) {
				ans.add(new LinkedList<>(path));
				return ;
			}
			
			for(int i = index ;i < s.length(); i++) {
				if(!isPalindrome(s,index,i)) {
					continue;
				}
				path.add(s.substring(index, i+1));
				process(i+1,path,ans,s);
				path.removeLast();
			}
			
		}
		
		/**
		 * leetcode 131  题目  恢复训练
		 * 下面直接写递归的 （recursion 的过程）
		 *以 集合的角度 去理解 （这个 递归里面嵌套 for 循环的  这种情况）
		 */
		
		public static List<List<String>> solutionAgain(String s){
			List<List<String>> ans = new ArrayList<>();
			Deque<String> path = new ArrayDeque<>();
			processAgain(s,0,ans,path);
			return ans;
		}
		
		
	 public static void processAgain(String s,int index,List<List<String>> ans,Deque<String> path) {
		 if(index == s.length()) {
			 // 这个basecase 有点奇怪 但是 根据题意才能写出来正确的 basecase
			 //  收集 叶子 节点 （结果集） 只有 满足的情况 才能 才能进入递归的这里
			 ans.add(new ArrayList<>(path));
			 return ;			 
		 }
		 
		 for(int i = index ;i < s.length(); i++) {
			 //  只有 是 回文字符串才会进入  下一次的递归
			 if(judge(s,index,i)) {
				 path.addLast(s.substring(index, i + 1));
				 processAgain(s,i + 1,ans,path);
				 path.removeLast();
			 }
			 
		 }
		 
	 }
	public static boolean judge(String s,int start,int end) {
		for(int i = start,j = end;j > i;i++,j--) {
			if(s.charAt(i) != s.charAt(j))
				return false;
		}
		return true;
	}
	/**
	 * 递归 改成 dp
	 * 这个题 还是 有些特殊性在里面的
	 * 但是 从目前的 leetcode 的效果 来看
	 * 优化好像没什么区别（至少 leetcode 的 时间 没有什么区别）
	 * 但是这种思想还是要学习一下的
	 * 感觉上是 有 优化的 
	 * 但是 结果 显示的效果好像是没有什么 优化效果
	 */
	public static void memorySearch(String s,List<List<String>> ans,Deque<String> path,
			int dp[][],int index) {
		if(index == s.length()) {
			ans.add(new ArrayList<>(path));
			return ;
		}
		for(int i = index ;i < s.length(); i++) {
			// == 0  表示就是没判断过  那就去判断 判断之后 （记录下来）
			if(dp[index][i] == 0)
				judge(s,index,i);
			// 如果 当前 切割的结果 不是 回文子串 直接 跳到下一个切割点 
			if(dp[index][i] == -1)
				continue;
			path.addLast(s.substring(index, i + 1));
			memorySearch(s,ans,path,dp,i + 1);
			path.removeLast();
		}
	}
	/**
	 * 不是返回的结果要 代表三种情况而是 dp [][]数组的值 要 能表示三种情况
	 * 1. 是回文串
	 * 2.不是回文串
	 * 3.没判断过
	 * @return
	 */
	public static boolean judge(String s,int start,int end,int dp[][]) {
		char str[] = s.toCharArray();
		for(int i = start ,j = end ;i < j;i++,j--) {
			if(str[i] != str[j]) {
				dp[start][end] = -1;
				return false;
			}
		}
		dp[start][end] = 1;
		return true;
	}
	
}
